/**
 * 给一个树，有边权，再给一个限制K，每个节点的度数最大为K
 * 问要如何删边使得既符合限制又能令边权和最大。
 * 令Ai是i子树上节点i最多连接K个儿子得到的最大和
 * Bi是i子树上节点i最多连接K-1个儿子（即留一个度给父亲）得到的最大和
 * 则A1是答案
 * 考虑如何求Ai，令j是i的儿子，且一共有m个。
 * 首先SIGMA{Aj}显然可以对Ai有贡献。
 * 在此基础上，可以替换某个Aj为Bj+Wij，最多替换K次或者K-1次即可。
 * 显然Bj+Wij比Aj大的越多，越要优先替换，因此排个序即可
 * 另一方面，显然Bj+Wij要大于Aj才有替换的必要
 */
class Solution {
using pii = pair<int, int>;
using vpii = vector<pii>;
using llt = long long;

struct _t{
    _t() = default;
    _t(int a, llt b, llt c):son(a),aw(b),bw(c){}
    int son;
    llt aw;
    llt bw;
    bool operator < (const _t & rhs) const {
        auto cha = bw - aw;
        auto rc = rhs.bw - rhs.aw;
        if(cha != rc) return cha > rc;
        return son < rhs.son;
    }
};

int N;
vector<map<int, int>> G;
vector<llt> A;
vector<llt> B;
vector<int> FlagA, FlagB;
int K;
public:
    long long maximizeSumOfWeights(vector<vector<int>>& edges, int k) {
        K = k;
        N = edges.size() + 1;
        G.assign(N + 1, {});
        for(const auto & e : edges){
            auto a = e[0] + 1;
            auto b = e[1] + 1;
            auto w = e[2];
            G[a].emplace(b, w);
            G[b].emplace(a, w);
        }
        FlagA.assign(N + 1, 0);
        FlagB.assign(N + 1, 0);
        A.assign(N + 1, 0);
        B.assign(N + 1, 0);
        dfs(1, 0);
        return A[1];
    }

    void dfs(int u, int p){
        /// <权值, 儿子节点, 0A1B>
        vector<_t> vec;

        for(const auto & e : G[u]){
            if(e.first == p) continue;
            dfs(e.first, u);
            vec.emplace_back(_t{e.first, A[e.first], B[e.first] + e.second});
        }

        sort(vec.begin(), vec.end());
        /// 首先最多选K个Aj能够得到的最大值
        for(int i=0;i<K&&i<vec.size();++i){
            A[u] += max(vec[i].aw, vec[i].bw);
        }
        for(int i=K;i<vec.size();++i) A[u] += vec[i].aw;

        for(int i=0;i<K-1&&i<vec.size();++i){
            B[u] += max(vec[i].aw, vec[i].bw);
        }
        for(int i=K-1;i<vec.size();++i) B[u] += vec[i].aw;
        return;        
    }



};
